/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86136
 * Date: 2024-11-28
 * Time: 13:46
 */
import java.util.*;

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
  }
class IntCmp implements Comparator<ListNode> {
    public int compare(ListNode o1, ListNode o2) {
        return o1.val - o2.val;
    }
}
class ListNodeCmp implements Comparator<ListNode> {
    @Override
    public int compare(ListNode o1, ListNode o2) {
        return o1.val - o2.val;
    }
}
public class Solution  {

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public static ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        if(lists == null) return null;
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new IntCmp());
        for (int i = 0; i < lists.size(); i++) {
            ListNode cur = lists.get(i);
            while(cur != null) {
                queue.offer(cur);
                cur = cur.next;
            }
        }
        ArrayList<ListNode> list = new ArrayList<>();
        ListNode cur = queue.poll();
        ListNode head = cur;
        list.add(head);
        while(!queue.isEmpty()) {
            ListNode top = queue.poll();
            cur.next = top;
            cur = top;
            top.next = null;
            list.add(top);
        }
        return head;
    }

    public static ListNode sortInList (ListNode head) {
        // write code here
        PriorityQueue<ListNode> queue = new PriorityQueue<>(new ListNodeCmp());
        if(head == null) return head;
        ListNode cur = head;
        while(cur != null) {
            queue.offer(cur);
            cur = cur.next;
        }
        ListNode newHead = queue.poll();
        ListNode tmp = newHead;
        while(!queue.isEmpty()) {
            tmp.next = queue.poll();
            tmp = tmp.next;
        }
        return newHead;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2= new ListNode(3);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        ListNode cur = sortInList(node1);
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }
    public static void main1(String[] args) {
        ListNode node1 = new ListNode(-6);
        ListNode node2= new ListNode(-4);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        ListNode node5 = new ListNode(-2);
        ListNode node6 = new ListNode(1);
        ListNode node7 = new ListNode(3);
        node5.next = node6;
        node6.next = node7;
        ListNode node8 = new ListNode(-10);
        ListNode node9 = new ListNode(-9);
        node8.next = node9;
        ListNode n1 = new ListNode(-9);
        ListNode n2 = new ListNode(-9);
        ListNode n3 = new ListNode(-8);
        ListNode n4 = new ListNode(-3);
        ListNode n5 = new ListNode(-2);
        ListNode n6 = new ListNode(-1);
        ListNode n7 = new ListNode(2);
        ListNode n8 = new ListNode(3);
        ListNode n9 = new ListNode(4);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n7;
        n7.next = n8;
        n8.next = n9;
        ListNode m1 = new ListNode(-10);
        ListNode m2 = new ListNode(-7);
        ListNode m3 = new ListNode(-5);
        ListNode m4 = new ListNode(1);
        m1.next = m2;
        m2.next = m3;
        m3.next = m4;
        ListNode q1 = new ListNode(-10);
        ListNode q2 = new ListNode(-8);
        ListNode q3 = new ListNode(-1);
        ListNode q4 = new ListNode(0);
        ListNode q5 = new ListNode(1);
        ListNode q6 = new ListNode(1);
        ListNode q7 = new ListNode(2);
        ListNode q8 = new ListNode(2);
        q1.next = q2;
        q2.next = q3;
        q3.next = q4;
        q4.next = q5;
        q5.next = q6;
        q6.next = q7;
        q7.next = q8;
        ArrayList<ListNode> lists = new ArrayList<>();
        lists.add(node1);
        lists.add(node5);
        lists.add(node8);
        lists.add(n1);
        lists.add(m1);
        lists.add(q1);
        ListNode head = mergeKLists(lists);
        while(head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}
